Lagrange dual problem

Definition

Define the Lagrange dual function $g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ as minimum value of the Lagrangian over $x$, i.e. for $\lambda \in \mathbb{R}^m$, $\nu \in \mathbb{R}^p$,

Notes

• if Lagrangian is unbounded below in $x$, then dual function takes value $- \infty$.
• dual function is pointwise infimum of family of affine functions of $(\lambda, \nu)$, hence concave even when optimization problem is not convex

See also

• Fenchel duality, Wolfe dual

References

1. https://en.wikipedia.org/wiki/Duality_(optimization)
2. S. P. Boyd and L. Vandenberghe, Convex optimization, 2004, p. 216. [Online]. Available: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf doi: 10.1017/CBO9780511804441 ISBN: 9780521833783